Чтение данных

Baseline

В качестве бейзлайна обучим логистическую регрессию, которая должна будет предсказывать для данного игрока и данного вопроса вероятнсоть его правильного ответа на него. Для этого сформируем вектор признаков вопроса и вектор признаков, характеризующих игрока.

Так как единственная информация, доступная нам про вопрос, это характеристика турнира, то будем описывать вопрос признаками, соответствующими турниру:

Замечание: можно было бы конечно использовать данные об ответе на вопрос (единственная информация, которая нам доступна по-вопросно из данных. Например, отношение правильных ответов к общему числу ответов на вопрос. Однако, с точки зрения модели такое делать некорректно: возникает утечка данных (подглядывание в ответы). Например, если бы доля правильных ответов равнялась 0, то это подсказало бы модели, что правильный ответ 0.

Вектор же игрока будем описывать его текущими достижениями:

Выборка будет формироваться следующим образом: для каждого турнира, для каждого участника, и для каждого вопроса мы добавляем вектор фичей и лейбл. После турнира пересчитывааем вектор признаков участника: в след турнире у него обновится вектор результатов. Турниры будем перебирать в порядке возрастания.

Для проверки результатов - зафиксируем вектора участников по состоянию на конец 2019 года. Каждый турнир 2020 года будем рассматривать независимо.

Подготовка данных

Генерация данных

Так как мы не разлтичаем по признакам вопросы с одного турнира между собой, то будем предсказывать долю правильных ответов на вопросы для турнира

Предсказание ранга команд

Так как для каждого игрока мы умеем предсказывать вероятность ответа на вопрос на турнире (условно "турнирный рейтинг игрока"), то для предсказания ранга команд можно поступить несколькими способами:

Воспользуемся третьим способом. Турнирный счет команды оценим как мат ожидания числа правильных ответов: $$R(team, tournament) = \sum_{q=1}^{Q}{1 - \prod_i(1-p_i)}=Q*(1 - \prod_i(1-p_i))$$

Так как множитель Q одинаковый для всех и не зависит от команд, то его можно опустить. Далее, так как мы хотим получить корреляцию между рангом и позицией, то лучше - меньший ранг -R. Финально: $$R(team, tournament) = - (1 - \prod_i(1-p_i)) \simeq \prod_i(1-p_i)$$

EM-алгоритм

Теперь постараемся учесть командный характер соревнования: участники выступают в команде, и мы знаем только ответила ли команда на вопрос или нет. Будем считать, что если хотя бы один из участников дал правильный ответ, то и команда дала правильный ответ (здесь мы предположили, что из всех мнений почему-то команда выбирает правильный с гарантией). Это нам дает такой результат: если команда дала неверный ответ, то значит ни один из участников не дал правильного ответа.

Полная вероятность при ответе на i-ый вопрос командой из K участников: $$p = p_1^ip_2^i...p_K^i + (1-p_1^i)p_2^i...p_K^i + (1-p_1^i)(1-p_2^i)...(1-p_K^i)$$ Где за $p_k^i$ обозначена вероятность ответить участника k на i-ый вопрос.

Если бы у нас были скрытые переменные $z_k^i$ - знал ли участник k ответ на i-ый вопрос, то было бы легко записать правдоподобие: $$LH(x_i, z_i) = \prod_k (p_k(x_i))^{z_i^k} * (1 - p_k(x_i))^{1-z_i^k}$$

И для всех данных (всех вопросов i) $$LH(x, z) = \prod_i \prod_k (p_k(x_i))^{z_i^k} * (1 - p_k(x_i))^{1-z_i^k}$$ $$log LH(x, z) = \sum_i \sum_k z_i^k p_k(x_i) + (1-z_i^k)(1 - p_k(x_i))$$

Заметим теперь, что в нашей модели $p_k(x_i)$ не зависит от конкретного вопроса, а только от соревнования, в котором появился данный вопрос. Следовательно, логарифм правдоподобия можно переписать: $$log LH(x, z) = \sum_c^{cup} \sum_q^{questions} \sum_m^{member} z_q^m p_m(x_c) + (1-z_q^m)(1 - p_m(x_c))$$

Будем пытаться предсказать вероятность $p_m(x_c)$ с помощью сигмоиды: $p_m(x_c) = \sigma(w, \eta(x_c, m))$

Для оценки $z_q^m$ будем использовать знание о том, был ли ответ команды ($y_q$) засчитан. Если ответа команды не было, то будем считать $z_q^m=0$ исходя из предположений модели. Если же был, то оценим $z_q^m$ как вероятность дать правильный ответ игроком: $$z_q^m = \begin{cases} \sigma(w, \eta(x_c, m)), & \mbox{if } y_q\mbox{ = 1} \\ 0, & \mbox{if } y_q\mbox{ = 0} \end{cases}$$

Подставив предложенный выше $z_q^m$ в логарифм правдоподобия, и учтя, что $p_m(x_c)$ не меняется в рамках соревнования, получим: $$log LH(x, z) = \sum_c^{cup} n_{y_q=1} (\sum_m^{member} z_q^m p_m(x_c) + (1-z_q^m)(1 - p_m(x_c))) + n_{y_q=0}(\sum_m^{member}1 - p_m(x_c)) = $$ $$=\sum_c^{cup}\sum_m^{member} n_{y_q=1}[p_m(x_c)(2z_q^m-1) + 1 - z_q^m] + n_{y_q=0}[1 - p_m(x_c)]$$ $$=\sum_c^{cup}\sum_m^{member} p_m(x_c)(n_{y_q=1}(2z_q^m-1)-n_{y_q=0})+n_{y_q=1}(1-z_q^m) + n_{y_q=0}$$

Таким образом получили EM-алгоритм:

Теперь постараемся учесть командный характер соревнования: участники выступают в команде, и мы знаем только ответила ли команда на вопрос или нет. Будем считать, что если хотя бы один из участников дал правильный ответ, то и команда дала правильный ответ (здесь мы предположили, что из всех мнений почему-то команда выбирает правильный с гарантией). Это нам дает такой результат: если команда дала неверный ответ, то значит ни один из участников не дал правильного ответа.

Хочется уметь предсказывать вероятность правильного ответа игрока на любой вопрос: $$p(y=1|x)=\sigma(\eta(x))=\frac{1}{1+e^{-\eta(x)}}$$

Однако, у нас есть для обучения некоторая подвыборка вопросов. Если обозначить за $s=1$ событие "попадание вопроса в выборку", то можно записать пропорции сэмплирования (вероятность попадания в выборку вопроса, на который игрок не ответит или ответит соответственно): $$\gamma_0 = p(s=1|y=0)=\frac{n_0}{(1-\pi)N}$$ $$\gamma_1 = p(s=1|y=1)=\frac{n_1}{\pi N}$$

Где $\pi$ - доля ответов, на которые может ответить участник.

Тогда: $$p(y=1|s=1,x)=\frac{p(s=1|y=1,x)p(y=1|x)}{p(s=1|y=0,x)p(y=0|x)+p(s=1|y=1,x)p(y=1|x)}=\frac{1}{\frac{p(s=1|y=0,x)(1-p(y=1|x))}{p(s=1|y=1,x)p(y=1|x)} + 1}=\frac{1}{\frac{\gamma_0}{\gamma_1}e^{-\eta(x)} + 1}=\frac{1}{e^{-\eta(x) - ln \frac{\gamma_1}{\gamma_0}} + 1}=\sigma(\eta(x)+ln \frac{\gamma_1}{\gamma_0})$$

Для нашего случая, мы имеем $n_n$ ($n_n \equiv n_{not\_correct}$) - количество наблюдаемых неправильных ответов игрока (равных в точности количеству неправильных ответов команды). Кроме этого, мы имеем некоторую вероятность правильного ответа игрока при условии правильного ответа команды: $\pi n_c$ ($n_c \equiv n_{correct}$), соответсвенно:

$$p(y=0|s=1)p(s=1)=\frac{n_n+(1-\pi)n_c}{n_c + n_n}; p(y=1|s=1)=\frac{\pi n_c}{n_c + n_n}$$$$\gamma_0 = p(s=1|y=0)=\frac{p(y=0|s=1)p(s=1)}{p(y=0)}=\frac{n_n+(1-\pi)n_c}{(n_c + n_n)(1-\pi)}p(s=1)$$$$\gamma_1 = p(s=1|y=1)=\frac{p(y=1|s=1)p(s=1)}{p(y=1)}=\frac{n_c}{n_c + n_n}p(s=1)$$

Так как нас интересует только их отношение, то:

$$\frac{\gamma_1}{\gamma_0}=\frac{n_c(1-\pi)}{n_n+(1-\pi)n_c}$$

Таким образом можно построить EM-алгоритм:

Генерация данных

Оценка алгоритма

Воспользуемся предыдущим способом построения ранга команд на основе вероятностей ответов игроков. Только теперь предскажем вероятность с помощью полученной модели в EM алгоритме

Отрисуем как менялись метрки до сходимости алгоритма

Выбор сложных вопросов

Для определения сложности вопроса - посчитаем для вопроса его ранк как: $$f(q) = \sum_{p \in \{not answered\}}r_p - \sum_{q \in \{answered\}}(1-r_p)$$ где ранк игрока возьмем как доля правильных ответов игрока: $$r_p = \frac{n_{correct}}{n_{correct} + n_{incorrect}}$$

Сложность туниров

Примерно соответствует ожиданиям

Можно также оценивать сложность турнира по сложности самого трудного вопроса